package com.itheima.leetcode.od.b.logicalsimulation;

import java.util.Arrays;

/**
 * (B卷,100分)- 路灯照明问题（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 在一条笔直的公路上安装了N个路灯，从位置0开始安装，路灯之间间距固定为100米。
 * 每个路灯都有自己的照明半径，请计算第一个路灯和最后一个路灯之间，无法照明的区间的长度和。
 * <p>
 * 输入描述
 * <p>
 * 第一行为一个数N，表示路灯个数，1<=N<=100000
 * <p>
 * 第二行为N个空格分隔的数，表示路灯的照明半径，1<=照明半径<=100000*100
 * <p>
 * 输出描述
 * <p>
 * 第一个路灯和最后一个路灯之间，无法照明的区间的长度和
 * <p>
 * 用例
 * <p>
 * 输入	2
 * <p>
 * 50 50
 * <p>
 * 输出	0
 * 说明	路灯1覆盖0-50，路灯2覆盖50-100，路灯1和路灯2之间(0米-100米)无未覆盖的区间。
 * <p>
 * 输入	4
 * <p>
 * 50 70 20 70
 * <p>
 * 输入
 * <p>
 * 解释
 * <p>
 * 路灯1 覆盖0-50
 * <p>
 * 路灯2 覆盖30-170
 * <p>
 * 路灯3 覆盖180-220
 * <p>
 * 路灯4 覆盖230-370
 * <p>
 * 输出	20
 * 说明	[170,180],[220,230]，两个未覆盖的区间，总里程为20
 * <p>
 * 题目解析
 * <p>
 * 本题可以转化为区间问题。
 * <p>
 * 每个路灯的位置都是确定，假设路灯的索引为 i，那么其位置就是 i * 100。
 * <p>
 * 根据第二行输入的路灯的照明半径数组arr，我们可以基于路灯的位置，求得路灯的照明范围区间
 * <p>
 * 假设center = i * 100，r = arr[i]，那么照明范围区间即为：[center - r, center + r]
 * <p>
 * 这样的话，我们就得到了一组区间。
 * <p>
 * 接下来，我们就需要将这些区间进行合并，合并后，求剩余没有交集的区间的间隙之和就是题解。
 * <p>
 * 这里区间合并是有技巧的，我们一般：
 * <p>
 * 先将区间按照起始位置进行升序
 * 如果起始位置相同，则再按照结束位置降序
 * 这样排序的好处是，所有区间都按照起始位置升序排序了，比如第一个ran[0]和第二个区间ran[1]，我们可以确定：ran[0].start <= ran[1].start
 * <p>
 * 由于这两个区间的起始位置关系已经确定了，判断这两个区间是否有交集，只要看ran[0].end和ran[1].start即可，如果ran[0].end > ran[1].start，则说明这两个区间有交集，可以合并。
 * <p>
 * 另外，如果ran[0]和ran[1]的起始位置相同的话，则上面排序还会按照结束位置进行降序，即必然ran[0].end >= ran[1].end。
 * <p>
 * 这样排序的好处是，后面区间的结束位置小于前面区间的结束位置时，可以直接放心并入前面区间，而不需要再进行起始位置相同的两个区间的结束位置比较。
 */
public class StreetLighting {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[][] ranges = new int[n][2];
        for (int i = 0; i < n; i++) {
            int center = i * 100;
            int r = sc.nextInt();
            ranges[i][0] = center - r;
            ranges[i][1] = center + r;
        }*/

        int n = 2;
        String input = "50 50";
        int[] arr = Arrays.stream(input.split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        int[][] ranges = new int[n][2];
        for (int i = 0; i < n; i++) {
            int center = i * 100;
            int r = arr[i];
            ranges[i][0] = center - r;
            ranges[i][1] = center + r;
        }

        System.out.println(getResult(n, ranges));
    }

    public static int getResult(int n, int[][] ranges) {
        int ans = 0;

        // 按起始位置升序，起始位置相同，则继续按结束位置降序
        Arrays.sort(ranges, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);

        int t = ranges[0][1]; // 上一个区间的结束位置

        for (int i = 1; i < n; i++) {
            // 当前区间的【开始位置，结束位置】
            int s = ranges[i][0];
            int e = ranges[i][1];

            // 有交集
            if (t >= s) {
                // 合并后的新区间将变为下一轮的上一个区间，t为新区间的结束位置
                t = Math.max(e, t);
            } else {
                // 没有交集，则统计区间间隙 s - t
                ans += s - t;
                // 当前区间变为下一轮的上一个区间，更新t
                t = e;
            }
        }

        return ans;
    }
}